package structure.linkedList1;

import java.util.LinkedList;

/**
 * Java实现单链表
 */
public class SingleLinkedList {

    private Node head;
    private int size;

    public SingleLinkedList() {
        size = 0;
        head = null;
    }

    public static void main(String[] args) {
        SingleLinkedList linkedList = new SingleLinkedList();
        linkedList.addNodeHead(34);
        linkedList.addNodeHead(67);
        System.out.println(linkedList);
        LinkedList linkedList1 = new LinkedList();
    }

    /**
     * 在链表头部插入（不用遍历链表，如果在尾部需要遍历）
     *
     * @param value
     */
    public void addNodeHead(Object value) {

        Node newNode = new Node(value);
        if (size == 0) {
            head = newNode;
        } else {
            newNode.next = head;
            head = newNode;
        }
        size++;
    }

    /**
     * 在链表尾部插入（不用遍历链表，如果在尾部需要遍历）
     *
     * @param value
     */
    public void addNodeTail(Object value) {
        Node temp = head;
        while (temp.next != null) {
            temp = temp.next;
        }
        temp.next = new Node(value);
        size++;
    }

    /**
     * 删除链表元素,默认删除头节点
     */
    public void deleteNode() {
        head = head.next;
        size--;
    }

    /**
     * 根据值查找某个节点
     *
     * @param value
     * @return
     */
    public Node find(Object value) {
        Node current = head;
        int count = 0;
        while (count < size) {
            if (current.value.equals(value)) {
                return current;
            } else {
                current = current.next;
            }
            count++;
        }
        return null;
    }

    /**
     * 根据位置查找某个节点
     *
     * @param index
     * @return
     */
    public Node find(int index) {
        if (index < 0 || index > size - 1) {
            return null;
        }
        if (index == 0) {
            return head;
        }
        Node current = head;
        int count = 0;
        while (current.next != null) {
            current = current.next;
            count++;
            if (count == index) {
                return current;
            }
        }
        return null;
    }

    /**
     * 删除某个位置的节点
     * bug: index =0 无法处理
     *
     * @param index
     */
    public void delete(int index) {
        if (index < 0 || index > size - 1) {
            return;
        }
        Node temp = head;
        int count = 0;
        while (temp.next != null) {
            if (index == count) {
                temp.next = temp.next.next;
                return;
            }
            count++;
            temp = temp.next;
        }
    }

    /**
     * 在某个位置插入节点
     *
     * @param index
     * @param value
     */
    public void insert(int index, Object value) {
        if (index < 0 || index > size - 1) {
            return;
        }
        Node newNode = new Node(value);
        if (index == 0) {
            newNode.next = head;
            head = newNode;
            return;
        }
        Node temp = head;
        int count = 1;
        while (count < index) {
            temp = temp.next;
            count++;
        }
        newNode.next = temp.next;
        temp.next = temp;
        size++;
    }

    /**
     * 迭代反转单链表
     *
     * @param node
     * @return
     */
    public Node reverse(Node node) {
        Node pre = null; // 返回结果，在头部添加
        Node next = null; // 标记下一个要反转的节点
        while (node != null) {
            next = node.next;

            // 将node添加到pre头部
            node.next = pre;
            pre = node;


            node = next;
        }
        return pre;
    }

    private class Node {
        private Object value; // 不是方法的变量是类的变量，所以在这可以用private修饰
        private Node next;

        private Node(Object value) {
            this.value = value;
        }
    }
}
